/**
 * 冒泡排序：适用于线性表的顺序存储和链式存储
 * 空间复杂度:O(1)
 * 时间复杂度:
 * 		最好的时间复杂度：初始序列有序:比较n-1次，移动次数为0；O(n)
 * 		最坏的时间复杂度：初始序列全为逆序列，需要进行n-1趟排序，
 * 						  第i趟要进行n-i次比较，每次比较移动元素3次进行交换;O(n^2)
 * 		平均时间复杂度：O(n^2)
 * 算法稳定性:稳定
 * 冒泡排序每一趟比较完都会把无序序列中最小的元素放在有序序列里
 */

#include <stdio.h>

#define bool int
#define true !0
#define false 0

void BubbleSort(int A[], int n);

void print(int a[], int n);


int main()
{
	int a[10]={12,43,16,22,63,98,66,90,20,26};
	BubbleSort(a,10);
	return 0;
}

void print(int a[], int n)
{
	for(int i=0;i<10;i++)
	{
		printf("%d ",a[i]);
	}
}

void BubbleSort(int A[], int n)
{
	int tmp;	
	for(int i=0;i<n;i++)
	{
		bool isChage=false;	//标志位，判断本趟冒泡是否发生交换，如果没有发生交换，说明已经排好序了
		for(int j=n-1;j>i;j--)//一趟冒泡过程
		{
			if(A[j-1]>A[j])//左边的元素大于右边的元素，则交换它们的位置
			{
				tmp=A[j-1];
				A[j-1]=A[j];
				A[j]=tmp;
				isChage=true;//设置标志位，表明本趟冒泡已经发生了交换
			}
		}
		if(isChage==false) break;//没有发生交换，说明已经排好序了，直接跳出循环
	}
	print(A,n);
	
}